#include "Stdafx.h"

#include "Engine.h"


namespace CzechMoveGen
{
	uint32 rayAttacks[4][32];

	void PrecalculateRayAttacks()
	{
		uint32 gen = 0;
		uint32 result = 0;
		for(int i = 0; i < 32; i++)
		{
			// left forward
			gen = 1 << i;
			result = 0;

			for(int j = 0; j < 8; j++)
			{
				int idx = LSB(gen) / 4;
				gen = idx % 2 == 0 ? (gen & LF1) << 3 : (gen & LF2) << 4;
				result |= gen;
			}

			rayAttacks[0][i] = result;

			// right forward
			gen = 1 << i;
			result = 0;

			for(int j = 0; j < 8; j++)
			{
				int idx = LSB(gen) / 4;
				gen = idx % 2 == 0 ? (gen & RF1) << 4 : (gen & RF2) << 5;
				result |= gen;
			}

			rayAttacks[1][i] = result;

			// left backwards
			gen = 1 << i;
			result = 0;

			for(int j = 0; j < 8; j++)
			{
				int idx = LSB(gen) / 4;
				gen = idx % 2 == 1 ? (gen & LB2) >> 4 : (gen & LB1) >> 5;
				result |= gen;
			}

			rayAttacks[2][i] = result;

			// right backwards
			gen = 1 << i;
			result = 0;

			for(int j = 0; j < 8; j++)
			{
				int idx = LSB(gen) / 4;
				gen = idx % 2 == 1 ? (gen & RB2) >> 3 : (gen & RB1) >> 4;
				result |= gen;
			}

			rayAttacks[3][i] = result;
		} // for

	}

	void DumpBitBoard(FILE* fp, uint32 bb)
	{
		bool bPrintBefore = true;
		for(int i = 31; i >= 0; i-=4)
		{
			for(int j = i - 3; j <= i; j++)
			{
				if(bPrintBefore)
					fprintf(fp, " ");

				int bit = bb & (1 << j);
				if(bit)
					fprintf(fp, "1");
				else
					fprintf(fp, "0");

				if(! bPrintBefore)
					fprintf(fp, " ");
			}

			fprintf(fp, "\n");
			bPrintBefore =  !bPrintBefore;
		}

		fprintf(fp, "\n");
	}

	void DumpRayAttacks()
	{
		FILE* fp = NULL;
		_wfopen_s(&fp, L"c:\\rayattacks.txt", L"w");
		if(fp)
		{
			for(int i = 0; i < 32; i++)	
			{
				fprintf(fp, "Position %d\n", i);

				for(int dir = 0; dir < 4; dir++)
				{
					fprintf(fp, "Direction %d\n", dir);
					DumpBitBoard(fp, rayAttacks[dir][i]);
				}
			}

			fclose(fp);
		}
	}


	void InitBitBoardGenerator()
	{
		PrecalculateRayAttacks();
	}

	void MakeWhiteKingMoves(BitBoard* bb, BitBoardMove* movelist, int& index, uint32 free)
	{
		int i = index;
		uint32 ray, blocker;
		uint32 occupied = ~free;
		uint32 tmp;
		int blockerSquare;
	
		int wk = bb->wk;
		while(wk)
		{
			int wkpos = LSB(wk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				ray = rayAttacks[j][wkpos];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);
					ray ^= rayAttacks[j][blockerSquare] | (1 << blockerSquare);
				}

				while(ray)
				{
					tmp = 1 << wkpos;
					tmp |= 1 << LSB(ray);
					movelist[i].wk = tmp;
					movelist[i].bk = 0;
					movelist[i].wm = 0;
					movelist[i].bm = 0;
					i++;

					ray = ray & (ray - 1); // delete least significant bit
				}
			} // for


			wk = wk &  (wk - 1); // delete least significant bit
		} // while

		index = i;
	}

	void MakeBlackKingMoves(BitBoard* bb, BitBoardMove* movelist, int& index, uint32 free)
	{
		int i = index;
		uint32 ray, blocker;
		uint32 occupied = ~free;
		uint32 tmp;
		int blockerSquare;
	
		int bk = bb->bk;
		while(bk)
		{
			int bkpos = LSB(bk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				ray = rayAttacks[j][bkpos];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);
					ray ^= rayAttacks[j][blockerSquare] | (1 << blockerSquare);
				}

				while(ray)
				{
					tmp = 1 << bkpos;
					tmp |= 1 << LSB(ray);
					movelist[i].bk = tmp;
					movelist[i].wk = 0;
					movelist[i].wm = 0;
					movelist[i].bm = 0;
					i++;

					ray = ray & (ray - 1); // delete least significant bit
				}
			} // for


			bk = bk &  (bk - 1); // delete least significant bit
		} // while

		index = i;
	}


	void MakeWhiteManMoves(BitBoard* bb, BitBoardMove* movelist, int& index, uint32 free)
	{
		int n = index;
		uint32 tmp;
		int m;

		if(bb->wm)
		{
			/* moves left forwards */
			/* I: columns 1357: just moves */
			m=((bb->wm&LF1)<<3)&free;
			/* now m contains a bit for every free square where a black man can move*/
			while(m)
			{
   				tmp=(m&-m); /* least significant bit of m */
				tmp=tmp|(tmp>>3); /* square where man came from */
				movelist[n].wm=tmp&NWBR; /* NWBR: not white back rank */
				movelist[n].wk=tmp&WBR; /*if stone moves to WBR (white back rank) it's a king*/
				movelist[n].bm=0;
				movelist[n].bk=0;
				n++;
      			m=m&(m-1);   /* clears least significant bit of m */
      		}

			 /* II: columns 2468 */
			m=((bb->wm&LF2)<<4)&free;
			while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp>>4);
				movelist[n].wm=tmp;
				movelist[n].wk=0;
				movelist[n].bm=0;
				movelist[n].bk=0;
				n++;
      			m=m&(m-1);
      		}
			 /* moves right forwards */
			 /* I: columns 1357 :just moves*/
			 m=((bb->wm&RF1)<<4)&free;
			 while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp>>4);
				movelist[n].wm=tmp&NWBR;
				movelist[n].wk=tmp&WBR;
				movelist[n].bm=0;
				movelist[n].bk=0;
				n++;
      			m=m&(m-1);
      		}

			 /* II: columns 2468 */
			m=((bb->wm&RF2)<<5)&free;
			while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp>>5);
				movelist[n].wm=tmp;
				movelist[n].wk=0;
				movelist[n].bm=0;
				movelist[n].bk=0;
				n++;
      			m=m&(m-1);
      		}
		} // if

		index = n;
	}

	void MakeBlackManMoves(BitBoard* bb, BitBoardMove* movelist, int& index, uint32 free)
	{
		int n = index;
		uint32 tmp;
		int m;

		if(bb->bm)
		{
			/* moves left backwards */
			/* II: columns 2468 ;just moves*/
			m=((bb->bm&LB2)>>4)&free;
			while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp<<4);
				movelist[n].wm=0;
				movelist[n].wk=0;
				movelist[n].bm=tmp&NBBR;
				movelist[n].bk=tmp&BBR;
				n++;
      			m=m&(m-1);
      		}
        
			/* I: columns 1357 */
			m=((bb->bm&LB1)>>5)&free;
			/* now m contains a bit for every free square where a white man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				tmp=tmp|(tmp<<5);
				movelist[n].wm=0;
				movelist[n].wk=0;
				movelist[n].bm=tmp;
				movelist[n].bk=0;
      			n++;
      			m=m&(m-1);   /* clears least significant bit of m */
      		}

			/* moves right backwards */

			/* II: columns 2468 : just the moves*/
			m=((bb->bm&RB2)>>3)&free;
			while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp<<3);
				movelist[n].wm=0;
				movelist[n].wk=0;
				movelist[n].bm=tmp&NBBR;
				movelist[n].bk=tmp&BBR;
				n++;
      			m=m&(m-1);
      		}
			/* I: columns 1357 */
			m=((bb->bm&RB1)>>4)&free;
			while(m)
   			{
				tmp=(m&-m);
				tmp=tmp|(tmp<<4);
				movelist[n].wm=0;
				movelist[n].wk=0;
				movelist[n].bm=tmp;
				movelist[n].bk=0;
      			n++;
      			m=m&(m-1);
      		}
		} // if

		index  = n;
	}


	int MakeMoveList(BitBoard *bb, BitBoardMove* movelist, bool bWhite)
	{
		int index = 0;
		uint32 free=~(bb->bm|bb->bk|bb->wm|bb->wk);
   
		if(bWhite == true)
		{
			MakeWhiteKingMoves(bb, movelist, index, free);
			MakeWhiteManMoves(bb, movelist, index, free);     
		}
		else
		{
			MakeBlackKingMoves(bb, movelist, index, free);
			MakeBlackManMoves(bb, movelist, index, free);
		}

		return index;
	}

	 // capture list 
	/////////////////////////////////////////////////////////////////////////////////////////////////////


	void WhiteManCapture1(BitBoard *p, BitBoardMove* movelist,int *n, BitBoardMove *partial, uint32 square)
	{
		/* partial move has already been executed. seek LFJ1 and RFJ1 */
		uint32 m,free,black;
		bool found=false;
		BitBoardMove next_partial,whole_partial;
		BitBoard q;

		free=~(p->bm|p->bk|p->wm|p->wk);
		black=p->bm|p->bk;
	   /* left forward jump */
		m=((((square&LFJ1)<<3)&black)<<4)&free;
		if(m)
   		{
			next_partial.wm=(m|(m>>7));
			next_partial.wk=0;
			next_partial.bm=(m>>4)&p->bm;
			next_partial.bk=(m>>4)&p->bk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			WhiteManCapture1(&q,movelist,n,&whole_partial,m);
     
			found=true;
		 } // if

		/* right forward jump */
		m=((((square&RFJ1)<<4)&black)<<5)&free;
		if(m)
		{
			next_partial.wm=(m|(m>>9));
			next_partial.wk=0;
			next_partial.bm=(m>>5)&p->bm;
			next_partial.bk=(m>>5)&p->bk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			WhiteManCapture1(&q,movelist,n,&whole_partial,m);
      
			found=true;
		}

		if(!found)
   		{
			movelist[*n]=*partial;
			(*n)++;
		}
	}

	void WhiteManCapture2(BitBoard *p, BitBoardMove* movelist,int *n, BitBoardMove *partial, uint32 square)
	{
		uint32 m,free,black;
		BitBoardMove next_partial,whole_partial;
		bool found=false;
		BitBoard q;

		free=~(p->bm|p->bk|p->wm|p->wk);
		black=p->bm|p->bk;
	   /* left forward jump */
		m=((((square&LFJ2)<<4)&black)<<3)&free;
		if(m)
   		{
			next_partial.wm=(m|(m>>7))&NWBR;
			next_partial.wk=(m|(m>>7))&WBR;
			next_partial.bm=(m>>3)&p->bm;
			next_partial.bk=(m>>3)&p->bk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			WhiteManCapture2(&q,movelist,n,&whole_partial,m);
      
			found=true;
		}

	   /* right forward jump */
		m=((((square&RFJ2)<<5)&black)<<4)&free;
		if(m)
   		{
			next_partial.wm=(m|(m>>9))&NWBR;
			next_partial.wk=(m|(m>>9))&WBR;
			next_partial.bm=(m>>4)&p->bm;
			next_partial.bk=(m>>4)&p->bk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			WhiteManCapture2(&q,movelist,n,&whole_partial,m);
      
			found=true;
		}

		if(!found)
   		{
			movelist[*n]=*partial;
			(*n)++;
		}
	}


	void BlackManCapture1(BitBoard *p, BitBoardMove* movelist,int *n, BitBoardMove* partial, uint32 square)
	{
		uint32 m,free,white;
		BitBoardMove next_partial,whole_partial;
		int found=0;
		BitBoard q;

		free=~(p->bm|p->bk|p->wm|p->wk);
		white=p->wm|p->wk;
		/* left backward jump */
		m=((((square&LBJ1)>>5)&white)>>4)&free;
		if(m)
   		{
			next_partial.bm=(m|(m<<9))&NBBR;
			next_partial.bk=(m|(m<<9))&BBR;
			next_partial.wm=(m<<4)&p->wm;
			next_partial.wk=(m<<4)&p->wk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			BlackManCapture1(&q,movelist,n,&whole_partial,m);
      
			found=1;
		}

	   /* right backward jump */
		m=((((square&RBJ1)>>4)&white)>>3)&free;
		if(m)
   		{
			next_partial.bm=(m|(m<<7))&NBBR;
			next_partial.bk=(m|(m<<7))&BBR;
			next_partial.wm=(m<<3)&p->wm;
			next_partial.wk=(m<<3)&p->wk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			BlackManCapture1(&q,movelist,n,&whole_partial,m);
      
			found=1;
		}

		if(!found)
   		{
			movelist[*n]=*partial;
			(*n)++;
		}
	}

	void BlackManCapture2(BitBoard *p, BitBoardMove* movelist,int *n, BitBoardMove *partial, uint32 square)
	{
		uint32 m,free,white;
		BitBoardMove next_partial,whole_partial;
		int found=0;
		BitBoard q;
	
		free=~(p->bm|p->bk|p->wm|p->wk);
		white=p->wm|p->wk;
	   /* left backward jump */
		m=((((square&LBJ2)>>4)&white)>>5)&free;
		if(m)
   		{
			next_partial.bm=(m|(m<<9));
			next_partial.bk=0;
			next_partial.wm=(m<<5)&p->wm;
			next_partial.wk=(m<<5)&p->wk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			BlackManCapture2(&q,movelist,n,&whole_partial,m);
      
			found=1;
		}

	   /* right backward jump */
		m=((((square&RBJ2)>>3)&white)>>4)&free;
		if(m)
   		{
			next_partial.bm=(m|(m<<7));
			next_partial.bk=0;
			next_partial.wm=(m<<4)&p->wm;
			next_partial.wk=(m<<4)&p->wk;
			q.bm=p->bm^next_partial.bm;
			q.bk=p->bk^next_partial.bk;
   			q.wm=p->wm^next_partial.wm;
   			q.wk=p->wk^next_partial.wk;
      
			whole_partial.bm=partial->bm^next_partial.bm;
			whole_partial.bk=partial->bk^next_partial.bk;
			whole_partial.wm=partial->wm^next_partial.wm;
			whole_partial.wk=partial->wk^next_partial.wk;
			BlackManCapture2(&q,movelist,n,&whole_partial,m);
      
			found=1;
		}

		if(!found)
		{
			movelist[*n]=*partial;
			(*n)++;
		}
	}


	void MakeWhiteManCaptures(BitBoard* p, BitBoardMove* movelist, int& n)
	{
		int m;
		uint32 tmp;
		BitBoardMove partial;
		uint32 black = 0, black2, free2;
		uint32 free = ~(p->bm|p->bk|p->wm|p->wk);
		BitBoard q;

		if(p->wm)
		{
			black=p->bm|p->bk;
      		m=((((p->wm&LFJ2)<<4)&black)<<3)&free;
			while(m)
   			{
				/* find a move */
				tmp=(m&-m); /* least significant bit of m */
				partial.wm=(tmp|(tmp>>7))&NWBR;  /* NWBR: not white back rank */
				partial.wk=(tmp|(tmp>>7))&WBR;  /*if stone moves to WBR (white back rank) it's a king*/
				partial.bm=(tmp>>3)&p->bm;
				partial.bk=(tmp>>3)&p->bk;
				/* toggle it */
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
				/* recursion */
				/* only if black has another capture move! */
				black2=p->bm|p->bk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( (((((tmp&LFJ2)<<4)&black2)<<3)&free2) | (((((tmp&RFJ2)<<5)&black2)<<4)&free2))
            		WhiteManCapture2(&q,movelist, &n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
				/* clears least significant bit of m, associated with that move. */
      			m=m&(m-1);
  			}

			m=((((p->wm&LFJ1)<<3)&black)<<4)&free;
      		/* now m contains a bit for every free square where a black man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.wm=(tmp|(tmp>>7));
				partial.wk=0;
				partial.bm=(tmp>>4)&p->bm;
				partial.bk=(tmp>>4)&p->bk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
            

				black2=p->bm|p->bk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LFJ1)<<3)&black2)<<4)&free2 ) | ( ((((tmp&RFJ1)<<4)&black2)<<5)&free2 ))
            		WhiteManCapture1(&q,movelist,&n,&partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}

			/* jumps right forwards with men*/
			m=((((p->wm&RFJ2)<<5)&black)<<4)&free;
      		/* now m contains a bit for every free square where a black man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.wm=(tmp|(tmp>>9))&NWBR;
				partial.wk=(tmp|(tmp>>9))&WBR;
				partial.bm=(tmp>>4)&p->bm;
				partial.bk=(tmp>>4)&p->bk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
            
				black2=p->bm|p->bk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LFJ2)<<4)&black2)<<3)&free2 ) | ( ((((tmp&RFJ2)<<5)&black2)<<4)&free2 ))
            		WhiteManCapture2(&q,movelist,&n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}

			m=((((p->wm&RFJ1)<<4)&black)<<5)&free;
      		/* now m contains a bit for every free square where a black man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.wm=tmp|(tmp>>9);
				partial.wk=0;
				partial.bm=(tmp>>5)&p->bm;
				partial.bk=(tmp>>5)&p->bk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
            
				black2=p->bm|p->bk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LFJ1)<<3)&black2)<<4)&free2 ) | ( ((((tmp&RFJ1)<<4)&black2)<<5)&free2 ))
            		WhiteManCapture1(&q,movelist, &n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}
		} // if
	}

	void MakeBlackManCaptures(BitBoard* p, BitBoardMove* movelist, int& n)
	{
		int m;
		uint32 tmp;
		BitBoardMove partial;
		uint32 white = 0, white2, free2;
		uint32 free = ~(p->bm|p->bk|p->wm|p->wk);
		BitBoard q;

		if(p->bm)
		{
			white=p->wm|p->wk;
      		/* jumps left backwards with men*/
      		m=((((p->bm&LBJ1)>>5)&white)>>4)&free;
      		/* now m contains a bit for every free square where a white man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.bm=(tmp|(tmp<<9))&NBBR;
				partial.bk=(tmp|(tmp<<9))&BBR;
				partial.wm=(tmp<<4)&p->wm;
				partial.wk=(tmp<<4)&p->wk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
				/* only if white has another capture move! */
				white2=p->wm|p->wk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LBJ1)>>5)&white2)>>4)&free2) | ( ((((tmp&RBJ1)>>4)&white2)>>3)&free2 ))
            		BlackManCapture1(&q,movelist, &n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
				m=m&(m-1);   /* clears least significant bit of m */
			}

			m=((((p->bm&LBJ2)>>4)&white)>>5)&free;
      		/* now m contains a bit for every free square where a white man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.bm=(tmp|(tmp<<9));
				partial.bk=0;
				partial.wm=(tmp<<5)&p->wm;
				partial.wk=(tmp<<5)&p->wk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;

				white2=p->wm|p->wk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LBJ2)>>4)&white2)>>5)&free2) | ( ((((tmp&RBJ2)>>3)&white2)>>4)&free2 ))
            		BlackManCapture2(&q,movelist,&n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}

			/* jumps right backwards with men*/
      		m=((((p->bm&RBJ1)>>4)&white)>>3)&free;
      		/* now m contains a bit for every free square where a white man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.bm=(tmp|(tmp<<7))&NBBR;
				partial.bk=(tmp|(tmp<<7))&BBR;
				partial.wm=(tmp<<3)&p->wm;
				partial.wk=(tmp<<3)&p->wk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;

				white2=p->wm|p->wk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LBJ1)>>5)&white2)>>4)&free2) | ( ((((tmp&RBJ1)>>4)&white2)>>3)&free2 ))
            		BlackManCapture1(&q,movelist, &n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}

			m=((((p->bm&RBJ2)>>3)&white)>>4)&free;
      		/* now m contains a bit for every free square where a black man can move*/
			while(m)
   			{
				tmp=(m&-m); /* least significant bit of m */
				partial.bm=(tmp|(tmp<<7));
				partial.bk=0;
				partial.wm=(tmp<<4)&p->wm;
				partial.wk=(tmp<<4)&p->wk;
				q.bm=p->bm^partial.bm;
   				q.bk=p->bk^partial.bk;
   				q.wm=p->wm^partial.wm;
   				q.wk=p->wk^partial.wk;
            
				white2=p->wm|p->wk;
				free2=~(p->wm|p->wk|p->bm|p->bk);
				if ( ( ((((tmp&LBJ2)>>4)&white2)>>5)&free2) | ( ((((tmp&RBJ2)>>3)&white2)>>4)&free2 ))
            		BlackManCapture2(&q,movelist, &n, &partial,tmp);
				else
				{
      				movelist[n]=partial;
      				n++;
				}
            
      			m=m&(m-1);   /* clears least significant bit of m */
			}
		}
	}


	bool MakeWhiteKingCaptures(BitBoard* bb, BitBoardMove* movelist, int& index, int ignoreDirection = -1, uint32 square = 255)
	{
		int i = index;
		uint32 ray, blocker, jumpedPattern;
		uint32 occupied = bb->wm | bb->bm | bb->wk | bb->bk;
		uint32 tmp;
		int blockerSquare, jumpedSquare;
		bool bFound = false;
		BitBoardMove partial;
		BitBoard q;

	
		uint32 wk = bb->wk;
		uint32 black = bb->bm | bb->bk;
		uint32 jumpedBlack = 0;

		if(square != 255)
			wk = 1 << square;

		while(wk)
		{
			int wkpos = LSB(wk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				// for multiple jumps ignore direction back
				if(j == ignoreDirection)
					continue;
				ray = rayAttacks[j][wkpos];

				jumpedBlack = ray & black;
				if(! jumpedBlack) // no jumped figure, continue
					continue; 
				jumpedSquare = j < 2 ? LSB(jumpedBlack) : MSB(jumpedBlack);
				blocker = ray & occupied;
				blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);

				// if blocker square earlier, ignore
				if(j < 2)
				{
					if(blockerSquare < jumpedSquare)
						continue;
				}
				else
				{
					if(blockerSquare > jumpedSquare)
						continue;
				}

				// get next blocker after jump
				ray = rayAttacks[j][jumpedSquare];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);			
					ray ^= rayAttacks[j][blockerSquare]  | (1 << blockerSquare);
				}

				jumpedPattern = 1 << jumpedSquare;

				bool bMultipleJump = false;
				int startI = i;
				while(ray)
				{
					// record partial move
					tmp = 1 << wkpos;
					uint32 finalSquare = LSB(ray);
					tmp |= 1 << finalSquare;
					partial.wk = tmp;
					partial.bk = bb->bk & jumpedPattern;
					partial.wm = bb->wm & jumpedPattern;
					partial.bm = bb->bm & jumpedPattern;

					// prepare next position
					q.wk = bb->wk ^ partial.wk;
					q.bk = bb->bk ^ partial.bk;
					q.wm = bb->wm ^ partial.wm;
					q.bm = bb->bm ^ partial.bm;

					int oldI = i;			
					if(MakeWhiteKingCaptures(&q, movelist, i, 3 - j, finalSquare) == false)
					{
						if(bMultipleJump == false)
						{
							movelist[i++] = partial;
							bFound = true;
						}
					} // if
					else if(i > oldI)
					{
						int k = oldI;
						while(k < i)
						{
							movelist[k].wm ^= partial.wm;
							movelist[k].bm ^= partial.bm;
							movelist[k].wk ^= partial.wk;
							movelist[k].bk ^= partial.bk;
							k++;
						}				
						if(bMultipleJump == false)
						{
							memcpy(&movelist[startI], &movelist[oldI], (i - oldI) * sizeof(BitBoardMove));
							i = startI + (i - oldI);
						}

					
						bMultipleJump = true;
						bFound = true;
					}


					ray = ray & (ray - 1); // delete least significant bit
				}
			} // for


			wk = wk &  (wk - 1); // delete least significant bit
		} // while

		index = i;

		return bFound;
	}


	bool MakeBlackKingCaptures(BitBoard* bb, BitBoardMove* movelist, int& index, 
								int ignoreDirection = -1, uint32 square = 255)
	{
		int i = index;
		uint32 ray, blocker, jumpedPattern;
		uint32 occupied = bb->wm | bb->bm | bb->wk | bb->bk;
		uint32 tmp;
		int blockerSquare, jumpedSquare;
		bool bFound = false;
		BitBoardMove partial;
		BitBoard q;

	
		uint32 bk = bb->bk;
		uint32 white = bb->wm | bb->wk;
		uint32 jumpedWhite = 0;

		if(square != 255)
			bk = 1 << square;

		while(bk)
		{
			int bkpos = LSB(bk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				// for multiple jumps ignore direction back
				if(j == ignoreDirection)
					continue;
				ray = rayAttacks[j][bkpos];

				jumpedWhite = ray & white;
				if(! jumpedWhite) // no jumped figure, continue
					continue; 
				jumpedSquare = j < 2 ? LSB(jumpedWhite) : MSB(jumpedWhite);
				blocker = ray & occupied;
				blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);

				// if blocker square earlier, ignore
				if(j < 2)
				{
					if(blockerSquare < jumpedSquare)
						continue;
				}
				else
				{
					if(blockerSquare > jumpedSquare)
						continue;
				}

				// get next blocker after jump
				ray = rayAttacks[j][jumpedSquare];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);			
					ray ^= (rayAttacks[j][blockerSquare]) | (1 << blockerSquare);
				}

				jumpedPattern = 1 << jumpedSquare;

				bool bMultipleJump = false;
				int startI = i;
				while(ray)
				{
					// record partial move
					tmp = 1 << bkpos;
					uint32 finalSquare = LSB(ray);
					tmp |= 1 << finalSquare;
					partial.bk = tmp;
					partial.wk = bb->wk & jumpedPattern;
					partial.wm = bb->wm & jumpedPattern;
					partial.bm = bb->bm & jumpedPattern;

					// prepare next position
					q.wk = bb->wk ^ partial.wk;
					q.bk = bb->bk ^ partial.bk;
					q.wm = bb->wm ^ partial.wm;
					q.bm = bb->bm ^ partial.bm;

					int oldI = i;
					if(MakeBlackKingCaptures(&q, movelist, i, 3 - j, finalSquare) == false)
					{
						if(bMultipleJump == false)
						{
							movelist[i++] = partial;
							bFound = true;
						}
					} // if
					else if(i > oldI)
					{
						int k = oldI;
						while(k < i)
						{
							movelist[k].wm ^= partial.wm;
							movelist[k].bm ^= partial.bm;
							movelist[k].wk ^= partial.wk;
							movelist[k].bk ^= partial.bk;
							k++;
						}				
						if(bMultipleJump == false)
						{
							memcpy(&movelist[startI], &movelist[oldI], (i - oldI) * sizeof(BitBoardMove));
							i = startI + (i - oldI);
						}

					
						bMultipleJump = true;
						bFound = true;
					}

					ray = ray & (ray - 1); // delete least significant bit
				}
			} // for


			bk = bk &  (bk - 1); // delete least significant bit
		} // while

		index = i;

		return bFound;
	}


	bool TestWhiteKingCaptures(BitBoard* bb )
	{
		uint32 ray, blocker;
		uint32 occupied = bb->wm | bb->bm | bb->wk | bb->bk;
		int blockerSquare, jumpedSquare;
	
		uint32 wk = bb->wk;
		uint32 black = bb->bm | bb->bk;
		uint32 jumpedBlack = 0;


		while(wk)
		{
			int wkpos = LSB(wk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				ray = rayAttacks[j][wkpos];

				jumpedBlack = ray & black;
				if(! jumpedBlack) // no jumped figure, continue
					continue; 
				jumpedSquare = j < 2 ? LSB(jumpedBlack) : MSB(jumpedBlack);
				blocker = ray & occupied;
				blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);

				// if blocker square earlier, ignore
				if(j < 2)
				{
					if(blockerSquare < jumpedSquare)
						continue;
				}
				else
				{
					if(blockerSquare > jumpedSquare)
						continue;
				}

				// get next blocker after jump
				ray = rayAttacks[j][jumpedSquare];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);			
					ray ^= rayAttacks[j][blockerSquare]  | (1 << blockerSquare);
				}

				if(ray)
					return true;
			} // for


			wk = wk &  (wk - 1); // delete least significant bit
		} // while

		return false;
	}


	bool TestBlackKingCaptures(BitBoard* bb)
	{
		uint32 ray, blocker;
		uint32 occupied = bb->wm | bb->bm | bb->wk | bb->bk;
		int blockerSquare, jumpedSquare;

		uint32 bk = bb->bk;
		uint32 white = bb->wm | bb->wk;
		uint32 jumpedWhite = 0;

		while(bk)
		{
			int bkpos = LSB(bk); // get field of white king

			for(int j = 0; j < 4; j++)
			{
				ray = rayAttacks[j][bkpos];

				jumpedWhite = ray & white;
				if(! jumpedWhite) // no jumped figure, continue
					continue; 
				jumpedSquare = j < 2 ? LSB(jumpedWhite) : MSB(jumpedWhite);
				blocker = ray & occupied;
				blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);

				// if blocker square earlier, ignore
				if(j < 2)
				{
					if(blockerSquare < jumpedSquare)
						continue;
				}
				else
				{
					if(blockerSquare > jumpedSquare)
						continue;
				}

				// get next blocker after jump
				ray = rayAttacks[j][jumpedSquare];
				blocker = ray & occupied;
				if(blocker)
				{
					blockerSquare = j < 2 ? LSB(blocker) : MSB(blocker);			
					ray ^= (rayAttacks[j][blockerSquare]) | (1 << blockerSquare);
				}

				if(ray)
					return true;

			} // for


			bk = bk &  (bk - 1); // delete least significant bit
		} // while

		return false;
	}




	void ToggleMove(BitBoard *p, BitBoardMove *m)
	{
		p->bm^=m->bm;
		p->bk^=m->bk;
		p->wm^=m->wm;
		p->wk^=m->wk;
	}

	 // Test Capture Methods
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	bool TestMenCapture(BitBoard *p, bool bWhite)
	{
		uint32 black,white,free,m;

		if (bWhite == true)
		{
			black=p->bm|p->bk;
			white=p->wm|p->wk;
			free=~(black|white);
		
			m =((((white&LFJ2)<<4)&black)<<3);
			m|=((((white&LFJ1)<<3)&black)<<4);
			m|=((((white&RFJ1)<<4)&black)<<5);
			m|=((((white&RFJ2)<<5)&black)<<4);
			if(m & free)
				return true;
			return false;
		}
		else
		{
			black=p->bm|p->bk;
			white=p->wm|p->wk;
			free=~(black|white);

			m=((((black&LBJ1)>>5)&white)>>4);
			m|=((((black&LBJ2)>>4)&white)>>5);
			m|=((((black&RBJ1)>>4)&white)>>3);
			m|=((((black&RBJ2)>>3)&white)>>4);
			if(m & free)
				return true;
			return false;
		}
	}

	 // Evaluation functions
	//////////////////////////////////////////////////////////////////////////////////////////////////////

	int CalculateDefenceFactor(uint32 men, bool bWhite)
	{
		int defenceCount = 0;

		if(bWhite)
		{
			defenceCount += BitCount( ((men&LB1) >> 5) & men);
			defenceCount += BitCount( ((men&LB2) >> 4) & men);
			defenceCount += BitCount( ((men&RB1) >> 4) & men);
			defenceCount += BitCount( ((men&RB2) >> 3) & men);
		}
		else
		{
			defenceCount += BitCount( ((men&LF1) << 3) & men);
			defenceCount += BitCount( ((men&LF2) << 4) & men);
			defenceCount += BitCount( ((men&RF1) << 4) & men);
			defenceCount += BitCount( ((men&RF2) << 5) & men);
		}

		return defenceCount;
	}

	int CalculateMenMobility(BitBoard* bb, bool bWhite)
	{
		int count = 0;
		BitBoard moves[MAX_MOVES];
		
		uint32 free=~(bb->bm|bb->bk|bb->wm|bb->wk);
		
		if(bWhite)
		{
			MakeWhiteManMoves(bb, moves, count, free);
		}
		else
		{
			MakeBlackManMoves(bb, moves, count, free);
		}

		return count;
	}

	 // Final methods for generating moves
	/////////////////////////////////////////////////////////////////////////////////////////////////////////////

	int GenerateBitBoardMoves(BitBoard* bb, bool bWhite, BitBoardMove* movelist)
	{
		WATCH_START(T_BIT_GENERATOR);
		// number of moves
		int count = 0;

		if(bWhite == true)
		{
			// there is no sense to make special test capture methods for kings
		
			if(MakeWhiteKingCaptures(bb, movelist, count) == true) // if king moves found, exit
			{}
			else
			{
				if(TestMenCapture(bb, bWhite))
					MakeWhiteManCaptures(bb, movelist, count);
				else
					count = MakeMoveList(bb, movelist, bWhite);
			}
		}
		else
		{
			// there is no sense to make special test capture methods for kings
		
			if(MakeBlackKingCaptures(bb, movelist, count) == true) // if king moves found, exit
			{}
			else
			{

				if(TestMenCapture(bb, bWhite))
					MakeBlackManCaptures(bb, movelist, count);
				else
					count = MakeMoveList(bb, movelist, bWhite);
			}
		}

		WATCH_END(T_BIT_GENERATOR);

		// return number of moves added to the list
		return count;
	}

	int GenerateBitBoardCaptures(BitBoard* bb, bool bWhite, BitBoardMove* movelist)
	{
		WATCH_START(T_BIT_GENERATOR);
		// number of moves
		int count = 0;

		if(bWhite == true)
		{
			// there is no sense to make special test capture methods for kings
		
			if(MakeWhiteKingCaptures(bb, movelist, count) == true) // if king moves found, exit
			{}
			else
			{
				if(TestMenCapture(bb, bWhite))
					MakeWhiteManCaptures(bb, movelist, count);
			}
		}
		else
		{
			// there is no sense to make special test capture methods for kings
		
			if(MakeBlackKingCaptures(bb, movelist, count) == true) // if king moves found, exit
			{}
			else
			{

				if(TestMenCapture(bb, bWhite))
					MakeBlackManCaptures(bb, movelist, count);
			}
		}

		WATCH_END(T_BIT_GENERATOR);

		// return number of moves added to the list
		return count;
	}



	bool TestJump(BitBoard* bb, bool bWhite)
	{
		bool bResult = false;

		WATCH_START(T_TEST_JUMP);

		if(TestMenCapture(bb, bWhite))
			bResult = true;
		else
		{
			if(bWhite && bb->wk )
				bResult = TestWhiteKingCaptures(bb);
			else if(!bWhite && bb->bk)
				bResult = TestBlackKingCaptures(bb);
		}

		WATCH_END(T_TEST_JUMP);

		return bResult;
	}
}
